The present invention relates generally to communication systems, and more particularly to reducing the number of multicast routes maintained by a multicast routing device in a multicast communication network.
In today""s information age, communication networks are often used for transporting information from an information provider to one or more information consumers.
One technique for transporting information from an information provider to a group of information consumers over the communication network is known as xe2x80x9cmulticasting.xe2x80x9d Multicasting allows the information provider (referred to hereinafter as a xe2x80x9cmulticast sourcexe2x80x9d) to transmit a single unit of multicast information (referred to hereinafter as a xe2x80x9cmulticast packetxe2x80x9d) simultaneously to all information consumers (referred to hereinafter individually as a xe2x80x9cmulticast clientxe2x80x9d and collectively as xe2x80x9cmulticast clientsxe2x80x9d) in the multicast group, specifically by addressing the multicast packet to the multicast group using a multicast address. The multicast clients monitor the communication network fore multicast packets addressed to the multicast group.
In order to distribute multicast packets from a particular multicast source S to the multicast clients for a particular multicast group G, the multicast packet is routed through the communication network by a number of routers. The communication network may include multiple routing domains, and therefore the multicast packet may traverse multiple routing domains. Each router runs various routing protocols to determine, among other things, a xe2x80x9cnext hopxe2x80x9d for each packet based upon address information in the packets. Such routing information is used to establish a multicast distribution tree, and is maintained by each router in one or more routing tables (often referred to as a xe2x80x9crouting information basexe2x80x9d). In particular, each router maintains a unicast routing information base (URIB) that is used to determine the xe2x80x9cnext hopxe2x80x9d for unicast packets. Also, each multicast router maintains a multicast routing information base (MREB) that is used to determine the xe2x80x9cnext hopxe2x80x9d for multicast packets.
One well-known protocol for routing multicast packets within a multicast routing domain is known as Protocol Independent Multicast (PIM). PIM is so named because it is not dependent upon any particular unicast routing protocol for setting up a multicast distribution tree within the multicast routing domain. PIM has two modes of operation, specifically a sparse mode and a dense mode. PIM Sparse Mode (PIM-SM) is described in the document Internet Engineering Task Force (IETF) Request For Comments (RFC) 2362 entitled Protocol Independent Multicastxe2x80x94Sparse Mode (PIM-SM): Protocol Specification and published in June 1998, hereby incorporated by reference in its entirety. PIM Dense Mode (PIM-DM) is described in an Internet Draft of the Internet Engineering Task Force (IETF) entitled Protocol Independent Multicast Version 2 Dense Mode Specification, document draft-ietf-pim-v2-dm-03.txt (Jun. 7, 1999), hereby incorporated by reference in its entirety
In accordance with the PIM protocol, the various routers within a particular PIM domain establish a default multicast distribution tree, referred to as a xe2x80x9cshared tree,xe2x80x9d for each multicast group. Each shared tree is rooted at a Rendezvous Point (RP) router that acts as the distribution point of all multicast packets for the multicast group. Before a router can join the shared tree for a particular multicast group, the router must learn the identity of the multicast group RP router. A router learns the identity of the multicast group RP router by receiving a PIM Bootstrap Message including a list of all RP routers in the PIM domain. The router receives the PIM Bootstrap Message either from a Bootstrap Router (BSR), which sends the PIM Bootstrap Message to all routers in the PIM domain at predetermined intervals (typically every 60 seconds), or from a neighboring router, which sends the PIM Bootstrap Message to the router if and only if the neighboring router has lost contact with the router for a predetermined period of time (typically 105 seconds). Upon learning the identity of the multicast group RP router, or at any time thereafter, each router that supports a downstream multicast group member (i.e., multicast client) joins the shared tree by sending a PIM Join/Prune Message hop-by-hop toward the multicast group RP router. Each intermediate router that receives the PIM Join/Prune Message from a downstream router also joins the shared tree by forwarding the PIM Join/Prune Message toward the multicast group RP router.
The PIM domain may have a number of source networks that belong to the PIM domain itself. Multicast packets that originate within such intradomain source networks are not routed to other PIM domains. The routes associated with such intradomain source networks (referred to hereinafter as intra-source routes) are distributed by a unicast routing protocol and maintained in the URIB.
In order to route the multicast packet between PIM domains, border routers in each PIM domain (each referred to hereinafter as a Multicast Border Gateway Protocol or MBGP router) determine interdomain routes (referred to hereinafter as MBGP routes) for the (source, group) pair. The MBGP router is typically a Multicast Source Discovery Protocol (MSDP) router or a PIM Multicast Border Router (PMBR) that functions as a Border Gateway Protocol (BGP) router to receive and install MBGP routes. MSDP, PMBR, and BGP are described in IETF documents and are well-known in the art.
A multicast communication network may have a large number of multicast routes. Within a particular multicast router, the number of multicast routes affects the size of the MRIB (i.e., the amount of memory consumed by the MRIB), which in turn affects the time required to search the MREB for a particular multicast route. The number of multicast routes also affects the inter-router communication overhead required to distribute multicast routes among the various routers.
Thus, a need has remained for a technique that reduces the number of multicast routes maintained in the MRIB.
In accordance with one aspect of the invention, a single policy route is installed in the MRIB in place of multiple multicast routes. The policy route may be an aggregation of multicast routes that do not have a next hop device, or the policy route may be an aggregation of multicast routes for which the next hop device can be determined from the corresponding unicast routes. The policy route includes an indicator indicating whether the policy route is an aggregation of multicast routes that do not have a next hop device, in which case the policy route is designated a rejected policy route, or an aggregation of multicast routes for which the next hop device can be determined from the corresponding unicast routes, in which case the policy route is designated an accepted policy route.
In accordance with another aspect of the invention, a bootstrap router (BSR) collects policy routes and distributes the policy routes using a bootstrap message. In a preferred embodiment, the BSR router periodically sends a bootstrap message including all policy routes, and also sends a bootstrap message including only changed policy routes whenever the BSR router detects a policy route change. The bootstrap messages are propagated to all PIM routers in the PIM domain.
In accordance with another aspect of the invention, a router that receives a bootstrap message installs the policy routes in its MRIB.
In accordance with another aspect of the invention, the router finds the best, most-specific multicast route in the MREB for a source address, and uses the corresponding unicast route to determine the next hop device for the source address if the most-specific multicast route is an accepted policy route.
In accordance with another aspect of the invention, the router finds the best, mostspecific multicast route in the MRIB for a source address, and determines that there is no next hop device for the source address if the most-specific multicast route is a rejected policy route.